package common.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 原理:
 * 把数组分割成若干个桶，
 * 分别对桶内的每个数组进行排序
 * 合并每个桶
 *
 */
public class BucketSort implements Sort {

    @Override
    public void sort(int[] array) {
        int min = array[0];
        int max = array[0];

        // 找出最大值与最小值
        for (int i = 1; i < array.length; i++) {
            if (min > array[i]) {
                min = array[i];
            }
            if (max < array[i]) {
                max = array[i];
            }
        }

        int diff = max - min;
        if (diff == 0) {
            return;
        }

        // 设置桶的数量
        int bucketNum = diff / 5 + 1;
        List<List<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<>());
        }

        for (int i = 0; i < array.length; i++) {
            bucketList.get((array[i] - min) / diff).add(array[i]);
        }

        // 分别对每个桶排序(可以使用归并或者快排等其他排序算法)
        for (int i = 0; i < bucketNum; i++) {
            Collections.sort(bucketList.get(i));
        }

        // 合并
        int idx = 0;
        for (int i = 0; i < bucketList.size(); i++) {
            for (int j = 0; j < bucketList.get(i).size(); j++) {
                array[idx++] = bucketList.get(i).get(j);
            }
        }
    }
}
